不会乘法表怎么做乘法？这个远古的算法竟然可以！
👆点击“博文视点Broadview”，获取更多书讯
很多人都说背乘法表是他们教育经历中特别痛苦的一件事。问父母为什么要背乘法表，父母通常会说不背就不会做乘法。他们大错特错。
俄罗斯农夫乘法（Russian peasant multiplication, RPM）就是在不了解大部分乘法表的情况下进行大数相乘的方法。
这是一种算术方法，尽管它叫这个名字，但也可能是埃及人，或者与农民没什么关系。
RPM 的起源尚不清楚。一份名为《莱因德纸草书》的古埃及卷轴记载了该算法的一个版本，一些历史学家提出（几乎没有说服力的）猜想，推测这种算法是如何从古埃及学者传播到辽阔的俄罗斯农夫那里的。
不论历史细节如何，RPM 都是一种有趣的算法。
例如，计算89乘以18。俄罗斯农夫乘法的过程如下。
首先，创建两个相邻的列。第一列称为半列（halving），第一项是89。第二列是倍列（doubling），第一项是18（表1）。
表1 半/倍表 第一部分
先填半列。半列的每一行是前一项的值除以2，余数忽略不计。例如，89除以2等于44余1，所以把44写在半列的第二行（表2）。
表2 半/倍表 第二部分
不断除以2，每次都去掉余数，把结果写在下一行，直到最后得到1。接着，44 除以2是22，然后22的一半是11，然后再一半（去掉余数）是5，之后得到2，最后是1。将这些值写在半列，得到表3。
表3 半/倍表 第三部分
半列填完了。顾名思义，倍列的每一行是前一项的值乘以2。18 乘以2等于36， 因此倍列的第二行是36（表4）。
表4 半/倍表 第四部分
按照同样的规则继续向倍列填值：前一项乘以2。直到倍列与半列行数相同为止（表5）。
表5 半/倍表 第五部分
下一步，将半列值是偶数的整行删掉，结果得到表6。
表6 半/倍表 第六部分
最后，将倍列所有项相加，结果是1602。可以用计算器检查一下：89乘以18也行于1602。我们通过减半、翻倍和加法完成了乘法运算，这些都不需要背诵乘法表。为了理解为什么这种方法行得通，试着将倍列改写为18的倍数（表7）。
表7 半/倍表 第七部分
现在，倍列中有1、2、4、8……直到64，这些都是2的幂数，因此可以把它们写成 、 、 等。最终求和（即奇数行的倍列值相加）的时候，我们得到的是：
RPM 之所以有效取决于
仔细观察半列，就能理解为什么以上等式是正确的。我们把半列也写成 2 的幂 （表8）。从最后一行开始，自下而上进行更容易些。记住， 是1， 是 2。每一 行都乘以 ，其中半列值是奇数的行，还要加上 。可以看到这个表达式越来越像 上面的等式。到第一行，我们得到了一个表达式，简化后刚好就是 。
表8 半/倍表 第八部分
设置半列的行号第一行是 0，最后一行是 6，可以看到半列值为奇数的行号是 0、 3、4、6。现在，请注意这个关键模式：这些行号恰好是 89 的表达式中的指数。这不是巧合；我们构造半列的方式意味着这个2的幂之和表达式中的指数，恰好总是奇数值的行号。把这些行对应的倍列值相加，其实就是18乘以2的幂之和，这个幂之和刚好等于89，即18和89。
其实，RPM实际上是算法的算法。半列本身是一种算法实现，即寻找与第一个数相等的2的幂之和。2的幂之和也称89的二进制展开（binary expansion）。二进制是只用0和1表示数字的一种方法，近几十年来它变得极其重要，因为计算机以二进制存储信息。我们可以把 89 写成二进制即 1011001，在第 0、3、4、6（从右开始 数）位上都有 1，这和半列的奇数行号一样，也和前面等式的指数一样。我们可以将二进制中的1和0解释为 2 的幂之和的系数。举个例子，二进制的100 解释为
也就是4。再比如，二进制的1001解释为
也就是 9。运行这个小算法可得到 89 的二进制展开值，然后我们就可以轻松地 运行整个算法来完成乘法过程。
用 Python 实现 RPM 比较简单。假设我们要把两个数 n1和 n2相乘，首先，打开 一个 Python 脚本，定义以下变量：
n1 = 89n2 = 18接下来，开始处理半列。如上所述，半列的第一个值是其中一个乘数：
halving = [n1]下一项是 halving[0]/2，去掉余数。在 Python 中，使用 math.floor()函数 实现。这个函数返回小于给定数字的最大整数。例如，半列的第二项计算如下：
import mathprint(math.floor(halving[0]/2))在Python运行后，结果是 44。
以同样的方式对半列的每一行进行迭代，直至得到1结束：
while(min(halving) > 1): halving.append(math.floor(min(halving)/2))使用append()方法将结果拼接起来。while循环的每次迭代，是将上一个值的1/2附加到 halving 向量，使用math.floor()函数忽略余数。
同样，对于倍列：从18开始，然后循环。这个循环的每次迭代，是将上一个值乘以2添加到倍列，当倍列的长度与半列的长度相等时停止：
doubling = [n2]while(len(doubling) < len(halving)): doubling.append(max(doubling) * 2)最后，将两个列放在一个名为half_double的数据框中：
import pandas as pdhalf_double = pd.DataFrame(zip(halving,doubling))这里我们导入了Python模块pandas。这个模块处理表很方便。在本例中，我们使用了zip命令，顾名思义，该命令将having和 doubling链接起来，就像拉链将衣服的两边连接在一起一样。
这两组数字（having 和 doubling）一开始是独立的列表（list），打包后转换为一个pandas数据框，然后作为两个对齐列存储在表5那样的表中。
由于对齐并打包在一起，所以引用任意一行将返回完整的行，包括半列和倍列的元素，比如表5的第三行，是22和72。对这些行进行引用和处理，删掉不想要的行，将表5转换为表6。
现在，我们需要删除半列值是偶数的行。使用Python的%（取模）运算符测试奇偶性，返回除法的余数。如果数字x是奇数，那么x%2等于1。执行下面这行代码， 则只保留半列值是奇数的行：
half_double = half_double.loc[half_double[0]%2 == 1,:]这里使用pandas模块的loc函数选择想要的行。使用 loc 时，在它后面的方 括号中指定我们想要选择的行和列。在方括号内按顺序指定行和列，用逗号分隔，格式是[行, 列]。例如，如果想要索引为4的行、索引为1的列，可以写为 half_double.loc[4,1]。
这个例子使用了一个逻辑表达式：半列值是奇数的所有 行。用 half_double[0]指定半列，半列的索引为 0；用%2 == 1 指定奇数；在逗号 之后使用冒号指定所有列，这是得到所有列的一种快捷方式。
最后，对剩下的倍列进行简单加和：
answer = sum(half_double.loc[:,1])这里我们又用到了 loc。在方括号内使用冒号指定所有行，逗号后面指定索引为1的倍列。注意，如果计算18 × 89——即把18 放在半列、89放在倍列，可以更快更容易地完成。我鼓励你去尝试一下，看看有什么提升。一般来说，如果将较小的乘数放在半列、较大的乘数放在倍列，RPM运行更快。
对于那些已经记住了乘法表的人来说，RPM似乎毫无意义。但是除了它的历史魅力，RPM还有几个值得学习的原因。
首先，RPM表明，即使是像乘法这样枯燥的事情，也可以通过多种方法来实现，而且是创造性方法。为了某个事情学会一种算法并不意味着它就是唯一的或最好的算法——对新的、潜在的更好的方法要敞开心扉。
RPM可能比较慢，但是它不需要消耗太多内存，因为它不要求掌握乘法表的大部分知识。有时候为了降低内存需求而牺牲一点速度是非常有用的，很多情况下我们设计和实现算法的时候，这种速度和内存的权衡是一个重要的考虑因素。
正如很多最佳算法那样，RPM 还体现了两种截然不同的理念之间的关系。二进制扩展好像看起来不过是猎奇，只有晶体管工程师感兴趣，对外行人或者专业程序员都没什么用处。
但是，RPM 展示了数字的二进制展开与一种便捷的乘法方法之间的深层联系，这个乘法方法只需要最低限度的乘法表知识。这便是你需要不断学习的另一个原因：你永远不知道什么时候一些看似无用的事实可能会成为强大算法的基础。
▼
除了俄罗斯农夫乘法，还有一些远古起源的算法，比如欧几里得算法、来自日本的生成幻方的算法等，如果大家想要继续了解的话，可以阅读《算法深潜：勇敢者的Python探险》一书。
这是一本内容广泛的Python算法书。你将看到很多很有意思的算法，包括：搜索、排序和最优化算法；以人为本的算法，帮助人们确定如何接球；先进的高级算法，比如机器学习和人工智能相关算法；以及古代文明时期的算法，比如数字相乘、寻找最大公约数以及幻方生成算法。
本书将带你学习：
◎生成Voronoi图，用于各种几何应用
◎使用算法构建聊天机器人、赢得棋类比赛、解决数独谜题
◎编写梯度上升和下降算法的代码，求解函数的最大值和最小值
◎使用模拟退火算法实现全局最优化
◎构建一个预测个人幸福的决策树
◎使用算法进行代码调试、收益最大化以及随机数生成
◎衡量算法的效率和速度
此外，本书还探索在纯数学中有用的算法，并学习如何基于数学思想改进算法。
跟着本书边做边学，你将了解当今许多超强算法的烦琐细节，包括如何在Python 3中编程实现这些算法，以及如何衡量和优化算法性能。
扫码了解本书详情
如果喜欢本文欢迎 在看丨留言丨分享至朋友圈 三连
热文推荐
▼点击阅读原文，了解本书详情~